/*
你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）

你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶 。

当车得到指令 "A" 时, 将会做出以下操作： position += speed, speed *= 2。

当车得到指令 "R" 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1 ；否则将车速调整为 speed = 1。  (当前所处位置不变。)

例如，当得到一系列指令 "AAR" 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。

现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。

 

示例 1:
输入: 
target = 3
输出: 2
解释: 
最短指令列表为 "AA"
位置变化为 0->1->3
示例 2:
输入: 
target = 6
输出: 5
解释: 
最短指令列表为 "AAARA"
位置变化为 0->1->3->7->7->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/race-car
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>
#include <queue>
using namespace std;

class Solution
{
public:
    int racecar(int target)
    {
        queue<pair<int, int>> q{{{0, 1}}};
        unordered_set<string> visit{"0,1"};
        int res = 0;
        while (q.size())
        {
            for (int sz = q.size(); sz > 0; sz--)
            {
                auto [pos, speed] = q.front();
                q.pop();
                if (pos == target)
                    return res;
                vector<pair<int, int>> nexts = {{pos + speed, speed * 2}, {pos, speed > 0 ? -1 : 1}};
                for (auto &[pos, speed] : nexts)
                {
                    string k = to_string(pos) + "," + to_string(speed);
                    if (!visit.count(k) && pos > 0 && pos < 2 * target)
                    {
                        visit.emplace(k);
                        q.emplace(pos, speed);
                    }
                }
            }
            res++;
        }
        return res;
    }
};